//实现一个基本的计算器来计算一个简单的字符串表达式的值。
//
// 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
//
// 示例 1:
//
// 输入: "1 + 1"
//输出: 2
//
//
// 示例 2:
//
// 输入: " 2-1 + 2 "
//输出: 3
//
// 示例 3:
//
// 输入: "(1+(4+5+2)-3)+(6+8)"
//输出: 23
//
// 说明：
//
//
// 你可以假设所给定的表达式都是有效的。
// 请不要使用内置的库函数 eval。
//
// Related Topics 栈 数学


package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class P224BasicCalculator {
    public static void main(String[] args) {
        Solution solution = new P224BasicCalculator().new Solution();
        //TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /**
         * https://leetcode-cn.com/problems/basic-calculator/solution/ji-ben-ji-suan-qi-by-leetcode/
         * 解法1.栈和不反转字符串
         *
         * @param str
         * @return
         */
        public int calculate(String str) {
            Stack<Integer> stack = new Stack();
            char[] chars = str.replace(" ", "").toCharArray();
            int result = 0;// For the on-going result
            int operand = 0;
            int sign = 1;// 1 means positive, -1 means negative
//            char l = '(';
//            char r = ')';
//            char s = '+';
//            char d = '-';

            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                if (Character.isDigit(c)) {
                    // Forming operand, since it could be more than one digit
                    operand = 10 * operand + (int) (c - '0');
                } else if (c != ' ') {
                    if (c == '+') {
                        // Evaluate the expression to the left,
                        // with result, sign, operand
                        result += sign * operand;
                        // Save the recently encountered '+' sign
                        sign = 1;
                        // Reset operand
                        operand = 0;
                    } else if (c == '-') {
                        result += sign * operand;
                        sign = -1;
                        operand = 0;
                    } else if (c == '(') {
                        // Push the result and sign on to the stack, for later
                        // We push the result first, then sign
                        stack.push(result);
                        stack.push(sign);
                        // Reset operand and result, as if new evaluation begins for the new sub-expression
                        sign = 1;
                        result = 0;
                    } else if (c == ')') {
                        // Evaluate the expression to the left
                        // with result, sign and operand
                        result += sign * operand;
                        // ')' marks end of expression within a set of parenthesis
                        // Its result is multiplied with sign on top of stack
                        // as stack.pop() is the sign before the parenthesis
                        result *= stack.pop();
                        // Then add to the next operand on the top.
                        // as stack.pop() is the result calculated before this parenthesis
                        // (operand on stack) + (sign on stack * (result from parenthesis))
                        result += stack.pop();
                        // Reset the operand
                        operand = 0;
                    }
                }

            }
            return result + (sign * operand);
        }


        /**
         * 解法2，栈和反转字符串
         *
         * @param s
         * @return
         */
        public int calculate2(String s) {
            int operand = 0;
            int n = 0;
            Stack<Object> stack = new Stack<Object>();

            for (int i = s.length() - 1; i >= 0; i--) {
                char ch = s.charAt(i);
                if (Character.isDigit(ch)) {
                    // Forming the operand - in reverse order.
                    operand = (int) Math.pow(10, n) * (int) (ch - '0') + operand;
                    n += 1;
                } else if (ch != ' ') {
                    if (n != 0) {
                        // Save the operand on the stack
                        // As we encounter some non-digit.
                        stack.push(operand);
                        n = 0;
                        operand = 0;
                    }
                    if (ch == '(') {
                        int res = evaluateExpr(stack);
                        stack.pop();
                        // Append the evaluated result to the stack.
                        // This result could be of a sub-expression within the parenthesis.
                        stack.push(res);
                    } else {
                        // For other non-digits just push onto the stack.
                        stack.push(ch);
                    }
                }
            }
            //Push the last operand to stack, if any.
            if (n != 0) {
                stack.push(operand);
            }
            // Evaluate any left overs in the stack.
            return evaluateExpr(stack);
        }
    }

    public int evaluateExpr(Stack<Object> stack) {
        int res = 0;
        if (!stack.empty()) {
            res = (int) stack.pop();
        }
        // Evaluate the expression till we get corresponding ')'
        while (!stack.empty() && !((char) stack.peek() == ')')) {
            char sign = (char) stack.pop();
            if (sign == '+') {
                res += (int) stack.pop();
            } else {
                res -= (int) stack.pop();
            }
        }
        return res;
    }
}

//leetcode submit region end(Prohibit modification and deletion)


